package com.sicheng.lc.周赛.分类.dp.线性;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/20 10:55
 */
public class 卖木头块 {
    //https://leetcode.cn/problems/selling-pieces-of-wood/
    public long sellingWood(int m, int n, int[][] prices) {
        int[][] price = new int[m + 1][n + 1];
        //dp[i,j]表示 高m宽n的木头卖出的最大价钱
        // dp[i,j] = 不切割直接卖
        // dp[i,j] = dp[i][k] + dp[i][j-k] 竖着切,k = [1,j/2] 向上取整
        // dp[i,j] = dp[k][j] + dp[i-k][j] 横着切,k = [1,i/2] 向上取整

        long[][] dp = new long[m + 1][n + 1];
        for (int[] p : prices) {
            price[p[0]][p[1]] = p[2];
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = price[i][j];
                int l1 = (int) Math.ceil(j * 1.0 / 2);
                int l2 = (int) Math.ceil(i * 1.0 / 2);
                for (int k = 1; k <= l1; k++)
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - k] + dp[i][k]);
                for (int k = 1; k <= l2; k++)
                    dp[i][j] = Math.max(dp[i][j], dp[k][j] + dp[i - k][j]);
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        卖木头块 solution = new 卖木头块();
        int[][] prices = {
                {1, 4, 2}, {2, 2, 7}, {2, 1, 3}
        };
        System.out.println(solution.sellingWood(3, 5, prices));
    }
}
